Programowanie strukturalne

Programowanie strukturalne – paradygmat programowania opierający się na podziale kodu źródłowego programu na procedury i hierarchicznie ułożone bloki z wykorzystaniem struktur kontrolnych w postaci instrukcji wyboru i pętli. Rozwijał się w opozycji do programowania wykorzystującego proste instrukcje warunkowe i skoki. Programowanie strukturalne zwiększa czytelność i ułatwia analizę programów, co stanowi znaczącą poprawę w stosunku do trudnego w utrzymaniu „spaghetti code” często wynikającego z użycia instrukcji goto.

Początki programowania strukturalnego przypadają na Lata 60. XX wieku, a ważnym głosem w dyskusji o programowaniu strukturalnym był list Edsgera Dijkstry Goto Statement considered harmful.

Język programowania zgodny z paradygmatem programowania strukturalnego nazywa się językiem strukturalnym.

Cechy charakterystyczne

Struktury kontrolne

Podstawowe struktury kontrolne jakie wymienia twierdzenie o programowaniu strukturalnym, z których możliwe jest zbudowanie dowolnego programu to:

• Sekwencja – wykonanie ciągu kolejnych instrukcji
• Wybór – w zależności od wartości predykatu wykonywana jest odpowiednia instrukcja. W językach programowania zazwyczaj reprezentowana przez słowa kluczowe if..then..else.
• Iteracja – wykonywanie instrukcji póki spełniony jest jakiś warunek. Reprezentowana w różnych wariantach jako pętle oznaczane między innymi przez: while, repeat, for lub do..until.

Każda ze struktur kontrolnych może być też rozumiana jako pojedyncza instrukcja. Według pierwotnych założeń struktury kontrolne powinny posiadać jedno wejście i jedno wyjście.

Podprogramy

Podprogramy pozwalają na wydzielenie pewnej grupy instrukcji i traktowania ich jako pojedynczej operacji, są dodatkowo mechanizmem abstrakcji.

Bloki

W językach programowania bloki odpowiadają sekwencjom instrukcji, umożliwiając budowanie programu przez komponowanie struktur kontrolnych – w miejscu, w którym umieścimy blok z instrukcjami jest on traktowany jak pojedyncza instrukcja.

W kodzie źródłowym programów bloki są wyróżniane na różne sposoby, przykładowo ograniczone przez if..fi jako blok dla instrukcji if w ALGOLU 68, czy dowolne bloki instrukcji obejmowanie poprzez BEGIN..END w Pascalu, PL/I, przy pomocy wcięć w Pythonie czy Haskellu lub poprzez nawiasy klamrowe w języku C i pochodnych.

Historia

Przed programowaniem strukturalnym

Pierwsze komputery były programowane wprost z użyciem kodu maszynowego lub z wykorzystaniem asemblera. Pierwsze asemblery przypadają na połowę lat 50. W 1954 roku Nathaniel Rochester napisał asembler dla IBM 701, natomiast w 1955 Stan Poley stworzył SOAP – asembler dla komputera IBM 650, początkowo programowanego wyłącznie przy pomocy kodu maszynowego. Kontrola przepływu w programie odbywała się głównie przy pomocy warunkowych i bezwarunkowych instrukcji skoku, w ówczesnych komputerach IBM określanych jako branch lub instrukcje transferu.

Wprowadzony w roku 1957 FORTRAN, pierwszy poważny język programowania wysokiego poziomu, główny nacisk kładł na formuły arytmetyczne. Występujące w nim struktury (a raczej instrukcje) kontrolne nie wykraczały daleko poza możliwości instrukcji skoku w asemblerach – język, poza skokiem bezwarunkowym, udostępniał przypisywalne (assigned goto) i obliczalne (computed goto) instrukcje skoku, oraz zbliżone do obliczalnego goto wyrażenie arytmetycznego (nie logicznego) if. Skoki były wykonywane do etykiet reprezentowanych przez wartości liczbowe. Dodatkowo występowała też prosta pętla.

ALGOL

Opublikowany w roku 1958 ALGOL 58 oraz jego dwa lata późniejsza, mocno rozwinięta wersja ALGOL 60, wprowadziły wiele kluczowych konstrukcji programistycznych, istotnych nie tylko z punktu widzenia programowania strukturalnego. Był to pierwszy język, w którym pojawił się koncept instrukcji złożonych – bloków – służących do grupowania instrukcji. Blok jest traktowany jako pojedyncza instrukcja i możliwe jest użycie go w miejscu dla niej przeznaczonym.

Język ALGOL wprowadził również fundamentalne dla programowania strukturalnego konstrukcje: logiczne instrukcje warunkowe if..then z opcjonalnym else, pętle for oraz instrukcję wyboru switch. Pozwolił też na deklarowanie procedur, w tym zagnieżdżonych w sobie, wraz z odpowiednim zasięgiem identyfikatorów. Instrukcja goto dalej pozostawała jednak ważnym elementem składniowym języka.

Podstawa teoretyczna

Jako fundament teorii programowania strukturalnego określa się twierdzenie o programowaniu strukturalnym. Jego autorstwo przypisuje się najczęściej ’Böhmowi i Giuseppe Jacopiniemu, wskazując jako źródło ich pracę Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules z maja 1966 roku. W swojej pracy pokazali oni, że dowolny program zawierający skoki (czyli dowolny graf przepływu), może zostać znormalizowany do odpowiadającego mu ustrukturyzowanego grafu – zbudowanego z trzech podstawowych struktur: $\Pi ,$ $\Delta$ oraz $\Omega ,$ wyrażającym odpowiednio: sekwencję, wybór oraz iterację. Ponieważ grafy przepływu mogą wyrażać dowolne funkcje obliczalne, to oznacza, że możemy też takie wyrazić przy pomocy tych podstawowych konstrukcji. W dalszej części pracy opisany jest język P′′ – pierwszy strukturalny język, dla którego udowodniono zupełność w sensie Turinga.

Twierdzenie Böhma i Jacopiniego nie mówi o tym w jaki sposób tworzyć dobre programy strukturalne lub je analizować. Prace nad tymi zagadnieniami odbywały się głównie na przełomie lat 60 i 70, z istotnym wkładem dokonamy przez Edsgera Dijkstrę, Roberta W. Floyda, Tony’ego Hoare’a, Ole-Johana Dahla, oraz Davida Griesa.

Dyskusja

Już na etapie projektowania języka ALGOL, w roku 1959, Heinz Zemanek rozważał ograniczenie użycia instrukcji goto, jednak jego uwagi zostały wtedy zignorowane. Niedługo później Hoare proponował ograniczenie użycia skoków tylko do wyjść alarmowych, natomiast w roku 1966 razem z Wirthem proponowali ograniczenia w postaci instrukcji wyboru case.

W debacie pomiędzy programistami dotyczącej popularyzacji programowania strukturalnego i ograniczeniu programowania opartego na goto najistotniejszym punktem jest praca Edsgera Dijkstry z 1974 roku A Case against GO TO Statemant opublikowana pod tytułem Goto Statement considered Harmful. Autor w sposób zdecydowany wyraża się przeciwko użyciu tej instrukcji:

Instrukcja go to powinna zostać usunięta z wszystkich „wysokopoziomowych” języków programowania (to znaczy z wszystkich poza – prawdopodobnie - czystym kodem maszynowym).

Odwołuje się też do twierdzenia Böhma i Jacopiniego, które umożliwia pokazanie, że goto jest instrukcją zbędną. Podaje przyczyny, przez które programy używające skoków są trudne w analizie. Dijkstra proponuje też odpowiednie ograniczenia na struktury kontrolne, jak na przykład Instrukcja opuszczenia, tak by dalej pozwalały na odpowiednią analizę, jeśli zestaw podstawowych instrukcji okazałby się zbyt ograniczający.

Jednym z pierwszych dużych komercyjnych projektów wykorzystujących programowanie strukturalne, który odniósł duży sukces było wykonane przez Harlana Millsa z IBM systemu indeksującego zbierane informacje dla New York Times.

Mimo kolejnych sukcesów związanych z aplikacją technik programowania strukturalnego, jak i rozwojowi teorii jej poświęconej, spora liczba programistów wciąż opierała się ograniczeniu lub wyeliminowaniu instrukcji goto z użycia. Donald Knuth w 1974 roku opublikował pracę Structured Programming with GoTo Statements, w której opisywał sytuacje gdzie użycie skoku upraszcza rozwiązanie bez wpływu na trudność w jego analizie.

W roku 1987 na łamach Communications of the ACM po liście Franka Rubina „GOTO Considered Harmful” Considered Harmful na nowo rozgorzała dyskusja dotycząca słuszności użycia goto, zarówno z głosami poparcia dla Rubina i użycia skoków, jak i mocnymi głosami przeciwko (razem z tytułami, stopniowo zawierającymi w coraz większej liczbie frazę „Considered Harmful”). Rubin twierdził:

Wiara, że GOTO są złe, stała się doktryną religijną, niepodważalną żadnymi dowodami

Zdaniem edytora była to największa wymiana listów w historii forum. Dyskusję uciął ostry list Dijkstry, poniekąd zawiedzionego poziomem dyskusji, jak i samymi próbami ponownej popularyzacji instrukcji goto.

Wpływ na języki programowania

Popularyzacja programowania strukturalnego zaowocowała wprowadzeniem konstrukcji programowania strukturalnego, często inspirowanych ALGOLEM, do języków programowania, które wcześniej ich nie posiadały, takich jak FORTRAN, COBOL czy BASIC.

Częste odstępstwa

O ile można obserwować zanik użycia goto, to istnieje niewiele czysto strukturalnych języków programowania. Najczęściej poza podstawowymi strukturami kontrolnymi pojawia się możliwość wczesnego wyjścia, łamiąc tym samym zasadę pojedynczego wyjścia z każdej struktury. Obsługa wyjątków również wykracza poza założenia programowania strukturalnego.

Wczesne wyjście

Najczęściej spotykana jest możliwość wyjścia z danej pętli lub podprogramu. Na poziomie podprogramu jest to zwykle instrukcja return. W przypadku pętli są to instrukcje break (przerwij daną pętlę) lub continue (przerwij daną iterację i przejdź do następnej). W czystym kodzie strukturalnym można napisać równoważne programy z wykorzystaniem dodatkowych instrukcji warunkowych, jednak może istotnie zwiększyć złożoność programów. Język C jest jednym z wczesnych przykładów wprowadzenia tego typu konstrukcji. Niektóre nowe języki programowania wprowadzają instrukcje „etykietowanego break”, które pozwalają opuścić więcej niż jeden poziom zagnieżdżonych pętli w pojedynczym kroku.

Wczesne wyjścia mogą powodować pewne trudności przy tworzeniu programów, związane na przykład z koniecznością zwalniania zaalokowanych zasobów przy każdym miejscu, w którym może być wykonany powrót z danego podprogramu. Występują różne podejścia: Pascal unika tych problemów nie dopuszczając tego typu konstrukcji, natomiast języki obiektowe wysokiego poziomu, takie jak C++ czy Java zawierają odpowiednie mechanizmy (RAII lub odśmiecanie pamięci) mające na celu ułatwienie pracy programiście.

Kent Beck, Martin Fowler wraz ze współautorami swoich książek na temat refaktoryzacji stwierdzają, że mocno zagnieżdżone bloki instrukcji warunkowych mogą być trudniejsze w zrozumieniu niż bardziej spłaszczona struktura z wieloma punktami wyjścia.

Pojedynczy punkt wyjścia nie jest tak naprawdę użyteczną regułą. Kluczem jest przejrzystość: Jeśli metoda jest prostsza z jednym punktem wyjścia, użyj jednego, w przeciwnym przypadku, użyj wielu

Herb Sutter i Andrei Alexandrescu również stwierdzają, że zasada pojedynczego wyjścia nie ma zastosowania w C++, jest tak za sprawą obsługi wyjątków i destruktorów, przez co każda funkcja może mieć wiele niejawnych punktów wyjścia.

Odmienne zdanie wyraża natomiast Bertrand Meyer, który w 2009 opisał break i continue jako „stare goto w owczej skórze” i mocno odradzał ich użycie.

Obsługa wyjątków

Badacze spierają się co do użycia wyjątków w kontekście programowania strukturalnego, jako że łamią one zasadę pojedynczego wyjścia. Cytując wcześniejsze badania (1999–2004) i podając własne, Westley Weimer i George Necula stwierdzają, że problem z wyjątkami polega na tym, że „tworzą ukryte ścieżki przepływu sterowania, o których programistom ciężko wnioskować”. Pojawiają się propozycje by sprowadzić wyjątki do pojedynczego wyjścia, jak i opinie, by pozostawić pełną dowolność w ich użyciu, jako że reguła pojedynczego wyjścia powstała przed pojawieniem się i popularyzacją wyjątków, a opakowywanie wyjątków by uczynić zgodnymi z regułą jednego wyjścia dodaje zbędne poziomy zagnieżdżenia utrudniając zrozumienie programów.

Zobacz też

• Paradygmat programowania
• Programowanie obiektowe
• Graf przepływu sterowania

Bibliografia

• Corrado Böhm, Giuseppe Jacopini. Flow diagrams, Turing machines and languages with only two formation rules. „Communications of the ACM”. 9 (5), s. 366–371, maj 1966. DOI: 10.1145/355592.365646. 
• Edsger Dijkstra. Go to statement considered harmful. „Communications of the ACM”. 11 (3), s. 147–148, marzec 1968. DOI: 10.1145/362929.362947.